////////////////////////////////////////////////////////////////////// 
// libsrc/StringMap.cpp 
// (c) 2000-2010 Goncalo Abecasis
// 
// This file is distributed as part of the Goncalo source code package   
// and may not be redistributed in any form, without prior written    
// permission from the author. Permission is granted for you to       
// modify this file for your own personal use, but modified versions  
// must retain this copyright notice and must not be distributed.     
// 
// Permission is granted for you to use this file to compile Goncalo.    
// 
// All computer programs have bugs. Use this file at your own risk.   
// 
// Sunday May 02, 2010
// 
 
#include "StringMap.h"

int StringMap::alloc = 8;

StringMap::StringMap(int startsize)
   {
   count = 0;
   size = (startsize + alloc) / alloc * alloc;
   strings = new ::String * [size];
   objects = new void * [size];
   };

StringMap::~StringMap()
   {
   for (int i = 0; i < count; i++)
      delete strings[i];
   delete [] strings;
   delete [] objects;
   }

void StringMap::Grow(int newsize)
   {
   if (newsize >= size)
      {
      if ((newsize >> 1) >= size)
         size = (newsize + alloc) / alloc * alloc;
      else
         {
         size = alloc;
         while (size <= newsize)
            size *= 2;
         }

      size = (newsize + alloc) / alloc * alloc;

      ::String ** newStrings = new ::String * [size];
      void     ** newObjects = new void * [size];

      for (int i = 0; i < count; i++)
         {
         newStrings[i] = strings[i];
         newObjects[i] = objects[i];
         }

      delete [] strings;
      delete [] objects;

      strings = newStrings;
      objects = newObjects;
      }
   }

int StringMap::Add(const ::String & key, void * object)
   {
   if (count == 0)
      {
      Grow(1);
      strings[0] = new ::String(key);
      objects[0] = object;
      return count++;
      }

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = key.SlowCompare(*(strings[probe]));

      if (test == 0)
         {
         objects[probe] = object;
         return probe;
         }

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int insertAt = left;
   int test = key.SlowCompare(*(strings[insertAt]));

   if (test == 0)
      {
      objects[insertAt] = object;
      return insertAt;
      }

   if (test > 0) insertAt++;

   Grow(count + 1);

   if (insertAt < count)
      {
      for (int i = count; i > insertAt; i--)
         {
         strings[i] = strings[i - 1];
         objects[i] = objects[i - 1];
         }
      }

   strings[insertAt] = new ::String(key);
   objects[insertAt] = object;
   count++;

   return insertAt;
   }

int StringMap::Find(const ::String & s,  void * (*create_object)())
   {
   if (!count)
      return create_object == NULL ? -1 : Add(s, create_object());

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = s.SlowCompare(*(strings[probe]));

      if (test == 0)
         return probe;

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int position = left;
   int test = s.SlowCompare(*(strings[left]));

   if (test == 0)
      return position;

   if (create_object == NULL)
      return -1;

   if (test > 0)
      position++;

   Grow(count + 1);

   if (position < count)
      {
      for (int i = count; i > position; i--)
         {
         strings[i] = strings[i - 1];
         objects[i] = objects[i - 1];
         }
      }

   strings[position] = new ::String (s);
   objects[position] = create_object();
   count++;

   return position;
   }

int StringMap::Find(const ::String & s) const
   {
   if (!count) return -1;

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = s.SlowCompare(*(strings[probe]));

      if (test == 0)
         return probe;

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int position = left;
   int test = s.SlowCompare(*(strings[left]));

   if (test == 0)
      return position;

   return -1;
   }

int StringMap::FindStem(const ::String & stem) const
   {
   if (!count) return -1;

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = strings[probe]->SlowCompareToStem(stem);

      if (test == 0)
         {
         if (left  < probe && strings[probe-1]->SlowCompareToStem(stem) == 0 ||
             right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0)
             return -2;

         return probe;
         }

      if (test > 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   if (strings[left]->SlowCompareToStem(stem) == 0)
      return left;

   return -1;
   }

int StringMap::FindFirstStem(const ::String & stem) const
   {
   if (!count) return -1;

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = strings[probe]->SlowCompareToStem(stem);

      if (test == 0)
         {
         while (left < probe && strings[probe-1]->SlowCompareToStem(stem) == 0)
            probe--;

         return probe;
         }

      if (test > 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   if (strings[left]->SlowCompareToStem(stem) == 0)
      return left;

   return -1;
   }

void * StringMap::CreateMap()
   {
   return (void *) new StringMap();
   }

void StringMap::Clear()
   {
   for (int i = 0; i < count; i++)
      delete strings[i];
   count = 0;
   }

void StringMap::Delete(int index)
   {
   count--;

   delete strings[index];

   for (int i = index; i < count; i++)
      {
      strings[i] = strings[i+1];
      objects[i] = objects[i+1];
      }
   }

// StringIntMap class
//

int StringIntMap::alloc = 8;

StringIntMap::StringIntMap(int startsize)
   {
   count = 0;
   size = (startsize + alloc) / alloc * alloc;
   strings = new ::String * [size];
   integers = new int[size];
   };

StringIntMap::~StringIntMap()
   {
   for (int i = 0; i < count; i++)
      delete strings[i];
   delete [] strings;
   delete [] integers;
   }

void StringIntMap::Grow(int newsize)
   {
   if (newsize >= size)
      {
      if ((newsize >> 1) >= size)
         size = (newsize + alloc) / alloc * alloc;
      else
         {
         size = alloc;
         while (size <= newsize)
            size *= 2;
         }

      ::String ** newStrings = new ::String * [size];
      int       * newIntegers = new int [size];

      for (int i = 0; i < count; i++)
         {
         newStrings[i] = strings[i];
         newIntegers[i] = integers[i];
         }

      delete [] strings;
      delete [] integers;

      strings = newStrings;
      integers = newIntegers;
      }
   }

int StringIntMap::Add(const ::String & key, int integer)
   {
   if (count == 0)
      {
      Grow(1);
      strings[0] = new ::String(key);
      integers[0] = integer;
      return count++;
      }

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = key.SlowCompare(*(strings[probe]));

      if (test == 0)
         {
         integers[probe] = integer;
         return probe;
         }

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int insertAt = left;
   int test = key.SlowCompare(*(strings[insertAt]));

   if (test == 0)
      {
      integers[insertAt] = integer;
      return insertAt;
      }

   if (test > 0) insertAt++;

   Grow(count + 1);

   if (insertAt < count)
      {
      for (int i = count; i > insertAt; i--)
         {
         strings[i] = strings[i - 1];
         integers[i] = integers[i - 1];
         }
      }

   strings[insertAt] = new ::String(key);
   integers[insertAt] = integer;
   count++;

   return insertAt;
   }

int StringIntMap::Find(const ::String & s, int defaultValue)
   {
   if (!count)
      return Add(s, defaultValue);

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = s.SlowCompare(*(strings[probe]));

      if (test == 0)
         return probe;

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int position = left;
   int test = s.SlowCompare(*(strings[left]));

   if (test == 0)
      return position;

   if (test > 0)
      position++;

   Grow(count + 1);

   if (position < count)
      {
      for (int i = count; i > position; i--)
         {
         strings[i] = strings[i - 1];
         integers[i] = integers[i - 1];
         }
      }

   strings[position] = new ::String (s);
   integers[position] = defaultValue;
   count++;

   return position;
   }

int StringIntMap::Find(const ::String & s) const
   {
   if (!count) return -1;

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = s.SlowCompare(*(strings[probe]));

      if (test == 0)
         return probe;

      if (test < 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   int position = left;
   int test = s.SlowCompare(*(strings[left]));

   if (test == 0)
      return position;

   return -1;
   }

int StringIntMap::FindStem(const ::String & stem) const
   {
   if (!count) return -1;

   int left = 0;
   int right = count - 1;

   while (right > left)
      {
      int probe = (left + right) / 2;
      int test  = strings[probe]->SlowCompareToStem(stem);

      if (test == 0)
         {
         if (left  < probe && strings[probe-1]->SlowCompareToStem(stem) == 0 ||
             right > probe && strings[probe+1]->SlowCompareToStem(stem) == 0)
             return -2;

         return probe;
         }

      if (test > 0)
         right = probe - 1;
      else
         left  = probe + 1;
      }

   if (strings[left]->SlowCompareToStem(stem) == 0)
      return left;

   return -1;
   }

void StringIntMap::Clear()
   {
   for (int i = 0; i < count; i++)
      delete strings[i];
   count = 0;
   }

int StringIntMap::GetCount(const ::String & key) const
   {
   int index = Find(key);
   return index == -1 ?  0 : integers[index];
   }

int StringIntMap::IncrementCount(const ::String & key)
   {
   int index = Find(key);

   if (index != -1)
      return ++(integers[index]);

   SetInteger(key, 1);
   return 1;
   }

int StringIntMap::DecrementCount(const ::String & key)
   {
   int index = Find(key);

   if (index != -1)
      return --(integers[index]);

   SetInteger(key, -1);
   return -1;
   }

void StringIntMap::Delete(int index)
   {
   count--;

   delete strings[index];

   for (int i = index; i < count; i++)
      {
      strings[i] = strings[i+1];
      integers[i] = integers[i+1];
      }
   }



 
